{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Triples with Bitwise AND Equal To Zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countTriplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按位与为零的三元组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，返回其中 <strong>按位与三元组</strong> 的数目。</p>\n",
    "\n",
    "<p><strong>按位与三元组</strong> 是由下标 <code>(i, j, k)</code> 组成的三元组，并满足下述全部条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; nums.length</code></li>\n",
    "\t<li><code>0 &lt;= j &lt; nums.length</code></li>\n",
    "\t<li><code>0 &lt;= k &lt; nums.length</code></li>\n",
    "\t<li><code>nums[i] &amp; nums[j] &amp; nums[k] == 0</code> ，其中 <code>&amp;</code> 表示按位与运算符。</li>\n",
    "</ul>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,1,3]\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>可以选出如下 i, j, k 三元组：\n",
    "(i=0, j=0, k=1) : 2 &amp; 2 &amp; 1\n",
    "(i=0, j=1, k=0) : 2 &amp; 1 &amp; 2\n",
    "(i=0, j=1, k=1) : 2 &amp; 1 &amp; 1\n",
    "(i=0, j=1, k=2) : 2 &amp; 1 &amp; 3\n",
    "(i=0, j=2, k=1) : 2 &amp; 3 &amp; 1\n",
    "(i=1, j=0, k=0) : 1 &amp; 2 &amp; 2\n",
    "(i=1, j=0, k=1) : 1 &amp; 2 &amp; 1\n",
    "(i=1, j=0, k=2) : 1 &amp; 2 &amp; 3\n",
    "(i=1, j=1, k=0) : 1 &amp; 1 &amp; 2\n",
    "(i=1, j=2, k=0) : 1 &amp; 3 &amp; 2\n",
    "(i=2, j=0, k=1) : 3 &amp; 2 &amp; 1\n",
    "(i=2, j=1, k=0) : 3 &amp; 1 &amp; 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,0,0]\n",
    "<strong>输出：</strong>27\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt; 2<sup>16</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [triples-with-bitwise-and-equal-to-zero](https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [triples-with-bitwise-and-equal-to-zero](https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]', '[0,0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        u = 1\n",
    "        for x in nums:\n",
    "            while u <= x:\n",
    "                u <<= 1\n",
    "        cnt = [0] * u\n",
    "        cnt[0] = len(nums)  # 直接统计空集\n",
    "        for m in nums:\n",
    "            m ^= u - 1\n",
    "            s = m\n",
    "            while s:  # 枚举 m 的非空子集\n",
    "                cnt[s] += 1\n",
    "                s = (s - 1) & m\n",
    "        return sum(cnt[x & y] for x in nums for y in nums)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "\n",
    "        cnt = [0] * (1 << 16)\n",
    "        for x in nums:\n",
    "            for y in nums:\n",
    "                cnt[x & y] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for m in nums:\n",
    "            m ^= 0xffff\n",
    "            s = m\n",
    "            \n",
    "            while True:  # 枚举 m 的子集（包括空集）\n",
    "                ans += cnt[s]\n",
    "                s = (s - 1) & m\n",
    "                if s == m: break\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        \"\"\" Hash / Bitmask \n",
    "        Hash: 我们可以先枚举任意两个数x和y，用哈希表或数组cnt统计它们的按位与结果x&y出现的次数\n",
    "        然后我们枚举x和y的按位与结果xy，再枚举z，如果xy&z=0，则将cnt[xy]的值加入答案\n",
    "        \"\"\"\n",
    "\n",
    "        # Solution 2: Bitmaks \n",
    "        # pre-processing: hash \n",
    "        total_cnt = 1 << 16\n",
    "        hashmap = [0] * total_cnt  # 65536\n",
    "        for x in nums:\n",
    "            for y in nums:\n",
    "                hashmap[x & y] += 1 \n",
    "\n",
    "        ans = 0 \n",
    "        for m in nums:\n",
    "            m ^= 0xffff  # the C of m \n",
    "            s = m \n",
    "            while True:\n",
    "                ans += hashmap[s]  # if s != 0, 意味着先前便利的xy在m的补集中 所以m*xy必为0\n",
    "                s = (s-1) & m  # 枚举遍历m的子集s\n",
    "                if s == m:\n",
    "                    break \n",
    "                \n",
    "        return ans \n",
    "        \n",
    "        \n",
    "\n",
    "        # solution 1: Hash\n",
    "        # cnt = Counter(i & j for i in nums for j in nums)\n",
    "\n",
    "        # ans = 0 \n",
    "        # for z in nums:\n",
    "        #     for xy, v in cnt.items():\n",
    "        #         if xy & z == 0:\n",
    "        #             ans += v \n",
    "        # return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        # res = 0\n",
    "        # n = len(nums)\n",
    "        # cnt = collections.Counter(x&y for x in nums for y in nums)\n",
    "        # for x in nums:\n",
    "        #     for y,k in cnt.items():\n",
    "        #         if x&y==0:\n",
    "        #             res += k  \n",
    "        # return res\n",
    "\n",
    "        cnt = [0]*(1<<16)\n",
    "        for x in nums:\n",
    "            for y in nums:\n",
    "                cnt[x&y] += 1\n",
    "        res = 0\n",
    "        for z in nums:\n",
    "            z ^= 0xffff\n",
    "            s = z\n",
    "            while True:\n",
    "                res += cnt[s]\n",
    "                s  = (s-1)&z\n",
    "                if s==z: break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "枚举所有nums[i] & nums[j] 的个数，采用hash表进行统计\n",
    "然后遍历k，如果 & 为零，则直接统计个数\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def countTriplets1(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter(x & y for x in nums for y in nums)\n",
    "        for x in nums:\n",
    "            for ky, val in cnt.items():\n",
    "                if x & ky == 0:\n",
    "                    ans += val\n",
    "        return ans\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * (1 << 16)\n",
    "        for x in nums:\n",
    "            for y in nums:\n",
    "                cnt[x & y] += 1\n",
    "        ans = 0\n",
    "        for m in nums:\n",
    "            m ^= 0xffff\n",
    "            s = m\n",
    "            while True:\n",
    "                ans += cnt[s]\n",
    "                s = (s - 1) & m\n",
    "                if s == m: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "枚举所有nums[i] & nums[j] 的个数，采用hash表进行统计\n",
    "然后遍历k，如果 & 为零，则直接统计个数\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def countTriplets1(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter(x & y for x in nums for y in nums)\n",
    "        for x in nums:\n",
    "            for ky, val in cnt.items():\n",
    "                if x & ky == 0:\n",
    "                    ans += val\n",
    "        return ans\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * (1 << 16)\n",
    "        for x in nums:\n",
    "            for y in nums:\n",
    "                cnt[x & y] += 1\n",
    "        ans = 0\n",
    "        for m in nums:\n",
    "            m ^= 0xffff\n",
    "            ans += cnt[m]\n",
    "            s = m\n",
    "            while s:\n",
    "                s = (s - 1) & m\n",
    "                ans += cnt[s]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        u = 1\n",
    "        for x in nums:\n",
    "            while u <= x:\n",
    "                u <<= 1\n",
    "        \n",
    "        records = [0] * u\n",
    "        records[0] = len(nums)\n",
    "\n",
    "        for m in nums:\n",
    "            m ^= u - 1\n",
    "            s = m\n",
    "            while s:\n",
    "                records[s] += 1\n",
    "                s = (s - 1) & m\n",
    "        \n",
    "        return sum(records[x & y] for x in nums for y in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = [0] * (1 << 16)\n",
    "        for x in nums:\n",
    "            for y in nums:\n",
    "                cnt[x & y] += 1\n",
    "        ans = 0\n",
    "        for m in nums:\n",
    "            m ^= 0xffff\n",
    "            s = m\n",
    "            while True:  # 枚举 m 的子集（包括空集）\n",
    "                ans += cnt[s]\n",
    "                s = (s - 1) & m\n",
    "                if s == m: break\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "        upper = 1\r\n",
    "        for x in nums:\r\n",
    "            while upper <= x:\r\n",
    "                upper <<= 1\r\n",
    "        \r\n",
    "        records = [0] * upper\r\n",
    "        records[0] = len(nums)\r\n",
    "\r\n",
    "        for m in nums:\r\n",
    "            m ^= upper - 1\r\n",
    "            s = m\r\n",
    "            while s:\r\n",
    "                records[s] += 1\r\n",
    "                s = (s-1) & m\r\n",
    "        \r\n",
    "        return sum(records[x & y] for x in nums for y in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "        upper = 1\r\n",
    "        for x in nums:\r\n",
    "            while upper <= x:\r\n",
    "                upper <<= 1\r\n",
    "        \r\n",
    "        records = [0] * upper\r\n",
    "        records[0] = len(nums)\r\n",
    "\r\n",
    "        for m in nums:\r\n",
    "            m ^= upper - 1\r\n",
    "            s = m\r\n",
    "            while s:\r\n",
    "                records[s] += 1\r\n",
    "                s = (s-1) & m\r\n",
    "        \r\n",
    "        return sum(records[x & y] for x in nums for y in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "\n",
    "        cnt = [0] * (1 << 16)\n",
    "        for x in nums:\n",
    "            for y in nums:\n",
    "                cnt[x & y] += 1\n",
    "        ans = 0\n",
    "        for m in nums:\n",
    "            m ^= 0xffff\n",
    "            s = m\n",
    "            while True:  # 枚举 m 的子集（包括空集）\n",
    "                ans += cnt[s]\n",
    "                s = (s - 1) & m\n",
    "                if s == m: break\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "        upper = 1\r\n",
    "        for x in nums:\r\n",
    "            while upper <= x:\r\n",
    "                upper <<= 1\r\n",
    "        \r\n",
    "        records = [0] * upper\r\n",
    "        records[0] = len(nums)\r\n",
    "\r\n",
    "        for m in nums:\r\n",
    "            m ^= upper - 1\r\n",
    "            s = m\r\n",
    "            while s:\r\n",
    "                records[s] += 1\r\n",
    "                s = (s-1) & m\r\n",
    "        \r\n",
    "        return sum(records[x & y] for x in nums for y in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "\r\n",
    "        # result = 0\r\n",
    "        \r\n",
    "        # cnt = Counter()\r\n",
    "        # for i in range(n):\r\n",
    "        #     for j in range(n):\r\n",
    "        #         cnt[nums[i] & nums[j]]+=1\r\n",
    "        \r\n",
    "        \r\n",
    "        # # i != j != k\r\n",
    "        # for i in range(n):\r\n",
    "        #     x = nums[i]\r\n",
    "        #     sub = x = x ^ 0xffff\r\n",
    "        #     while True:\r\n",
    "        #         if sub in cnt:\r\n",
    "        #             result += cnt[sub]\r\n",
    "        #         if sub == 0:\r\n",
    "        #             break\r\n",
    "        #         sub = (sub - 1) & x\r\n",
    "    \r\n",
    "        # return result\r\n",
    "        n = len(nums)\r\n",
    "        s = 16\r\n",
    "        a = [0] * (1<<s)\r\n",
    "        for item in nums:\r\n",
    "            a[item] +=1\r\n",
    "        def FWT(arr, rev):\r\n",
    "            for i in range(s):\r\n",
    "                for j in range(0, 1<<s, 1 << (i+1)):\r\n",
    "                    for k in range(1 << i):\r\n",
    "                        if not rev:\r\n",
    "                            arr[j|k] += arr[j|k|(1<<i)]\r\n",
    "                        else:\r\n",
    "                            arr[j|k] -= arr[j|k|(1<<i)]\r\n",
    "        FWT(a, False)\r\n",
    "        for i in range(1<<s):\r\n",
    "            a[i] = a[i] * a[i] * a[i]\r\n",
    "        FWT(a, True)\r\n",
    "        return a[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "\r\n",
    "        # result = 0\r\n",
    "        \r\n",
    "        # cnt = Counter()\r\n",
    "        # for i in range(n):\r\n",
    "        #     for j in range(n):\r\n",
    "        #         cnt[nums[i] & nums[j]]+=1\r\n",
    "        \r\n",
    "        \r\n",
    "        # # i != j != k\r\n",
    "        # for i in range(n):\r\n",
    "        #     x = nums[i]\r\n",
    "        #     sub = x = x ^ 0xffff\r\n",
    "        #     while True:\r\n",
    "        #         if sub in cnt:\r\n",
    "        #             result += cnt[sub]\r\n",
    "        #         if sub == 0:\r\n",
    "        #             break\r\n",
    "        #         sub = (sub - 1) & x\r\n",
    "    \r\n",
    "        # return result\r\n",
    "        n = len(nums)\r\n",
    "        s = 16\r\n",
    "        a = [0] * (1<<s)\r\n",
    "        for item in nums:\r\n",
    "            a[item] +=1\r\n",
    "        def FWT(arr, rev):\r\n",
    "            for i in range(s):\r\n",
    "                for j in range(0, 1<<s, 1 << (i+1)):\r\n",
    "                    for k in range(1 << i):\r\n",
    "                        if not rev:\r\n",
    "                            arr[j|k] += arr[j|k|(1<<i)]\r\n",
    "                        else:\r\n",
    "                            arr[j|k] -= arr[j|k|(1<<i)]\r\n",
    "        FWT(a, False)\r\n",
    "        for i in range(1<<s):\r\n",
    "            a[i] = a[i] * a[i] * a[i]\r\n",
    "        FWT(a, True)\r\n",
    "        return a[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "\r\n",
    "        # result = 0\r\n",
    "        \r\n",
    "        # cnt = Counter()\r\n",
    "        # for i in range(n):\r\n",
    "        #     for j in range(n):\r\n",
    "        #         cnt[nums[i] & nums[j]]+=1\r\n",
    "        \r\n",
    "        \r\n",
    "        # # i != j != k\r\n",
    "        # for i in range(n):\r\n",
    "        #     x = nums[i]\r\n",
    "        #     sub = x = x ^ 0xffff\r\n",
    "        #     while True:\r\n",
    "        #         if sub in cnt:\r\n",
    "        #             result += cnt[sub]\r\n",
    "        #         if sub == 0:\r\n",
    "        #             break\r\n",
    "        #         sub = (sub - 1) & x\r\n",
    "    \r\n",
    "        # return result\r\n",
    "        n = len(nums)\r\n",
    "        s = 16\r\n",
    "        a = [0] * (1<<s)\r\n",
    "        for item in nums:\r\n",
    "            a[item] +=1\r\n",
    "        def FWT(arr, rev):\r\n",
    "            for i in range(s):\r\n",
    "                for j in range(0, 1<<s, 1 << (i+1)):\r\n",
    "                    for k in range(1 << i):\r\n",
    "                        if not rev:\r\n",
    "                            arr[j|k] += arr[j|k|(1<<i)]\r\n",
    "                        else:\r\n",
    "                            arr[j|k] -= arr[j|k|(1<<i)]\r\n",
    "        FWT(a, False)\r\n",
    "        for i in range(1<<s):\r\n",
    "            a[i] = a[i] * a[i] * a[i]\r\n",
    "        FWT(a, True)\r\n",
    "        return a[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(x & y for x in nums for y in nums)\n",
    "        return sum(c for x, c in cnt.items() for y in nums if x & y == 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "\n",
    "        for i in nums:\n",
    "            for j in nums:\n",
    "                dic[i & j] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for i in nums:\n",
    "            for k, v in dic.items():\n",
    "                if i & k == 0:\n",
    "                    ans += v\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        for x in nums:\n",
    "            for y in nums:\n",
    "                cnt[x & y] += 1\n",
    "        for z in nums:\n",
    "            for k, v in cnt.items():\n",
    "                if not z & k:\n",
    "                    ans += v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        dic = Counter(x & y for x in nums for y in nums)\n",
    "        res = 0\n",
    "        for z in nums:\n",
    "            for k, v in dic.items():\n",
    "                if z & k == 0:\n",
    "                    res += v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        counter = Counter((x & y) for x in nums for y in nums)\n",
    "\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            sub = x = x ^ ((1 << 16) - 1)\n",
    "            while True:\n",
    "                if sub in counter:\n",
    "                    ans += counter[sub]\n",
    "                if sub == 0:\n",
    "                    break\n",
    "                sub = (sub - 1) & x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                cnt = nums[i] & nums[j]\n",
    "                if cnt not in dp:\n",
    "                    dp[cnt] = 0\n",
    "                dp[cnt] += 1\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for key in dp:\n",
    "                if nums[i] & key == 0:\n",
    "                    res += dp[key]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(x & y for x in nums for y in nums)\n",
    "        return sum(c for x, c in cnt.items() for y in nums if x & y == 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = Counter()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                d[nums[i] & nums[j]] += 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for k, v in d.items():\n",
    "                if nums[i] & k == 0:\n",
    "                    ans += v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(x & y for x in nums for y in nums)\n",
    "        return sum(c for x, c in cnt.items() for y in nums if x & y == 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        cnt=Counter()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                cnt[nums[i]&nums[j]]+=1\n",
    "        ans=0\n",
    "        for num in nums:\n",
    "            for k,v in cnt.items():\n",
    "                if num&k==0:\n",
    "                    ans+=v   \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        result = 0\r\n",
    "        \r\n",
    "        cnt = Counter()\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(n):\r\n",
    "                cnt[nums[i] & nums[j]]+=1\r\n",
    "        \r\n",
    "        \r\n",
    "        # i != j != k\r\n",
    "        for i in range(n):\r\n",
    "            for key, value in cnt.items():\r\n",
    "                if key & nums[i] == 0:\r\n",
    "                    result += value\r\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for a in nums:\n",
    "            for b in nums:\n",
    "                cnt[a&b]+=1\n",
    "\n",
    "        ret = 0\n",
    "        for x,c in cnt.items():\n",
    "            for v in nums:\n",
    "                if x&v==0:\n",
    "                    ret += c\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 得到 nums[i] & nums[j] 的种类以及出现次数\n",
    "        cnt = Counter((x & y) for x in nums for y in nums)\n",
    "\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            for mask, freq in cnt.items():\n",
    "                if x & mask == 0:\n",
    "                    ans += freq\n",
    "\n",
    "        return ans\n",
    "\n",
    "        # n = len(nums)\n",
    "        # visited = set()\n",
    "        # ans = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         for k in range(n):\n",
    "        #             if nums[i] & nums[j] & nums[k] == 0 and (i, j, k) not in visited:\n",
    "        #                 visited.add((i, j, k))\n",
    "        #                 ans += 1\n",
    "\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = collections.Counter((x & y) for x in nums for y in nums)\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            for mask, freq in cnt.items():\n",
    "                if (x & mask) == 0:\n",
    "                    ans += freq\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i in nums:\n",
    "            for j in nums:\n",
    "                dic[i&j] += 1\n",
    "                \n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            for k,v in dic.items():\n",
    "                if (i & k) == 0:\n",
    "                    res += v\n",
    "        return(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        c = collections.Counter(i&j for i in nums for j in nums)\n",
    "        return sum(c[j] for i in nums for j in c if i&j==0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        \n",
    "       cnt = Counter((x&y) for x in nums for y in nums)\n",
    "\n",
    "       ans = 0 \n",
    "       for x in nums:\n",
    "           for mask, freq in cnt.items():\n",
    "               if (x & mask ) == 0:\n",
    "                   ans += freq\n",
    "       return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        d=defaultdict(int)\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            d[nums[i]]+=1            \n",
    "            for j in range(i+1,n):\n",
    "                d[nums[i]&nums[j]]+=2\n",
    "        res=0\n",
    "        for num in nums:\n",
    "            for k,v in d.items():\n",
    "                if num&k==0:\n",
    "                    res+=v\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "        cnt = collections.Counter()\r\n",
    "        for a in nums:\r\n",
    "            for b in nums:\r\n",
    "                cnt[a & b] += 1\r\n",
    "        ans = 0\r\n",
    "        for a in nums:\r\n",
    "            for k, v in cnt.items():\r\n",
    "                if a & k == 0:\r\n",
    "                    ans += v\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        cnt = collections.Counter(x&y for x in nums for y in nums)\n",
    "        for x in nums:\n",
    "            for y,k in cnt.items():\n",
    "                if x&y==0:\n",
    "                    res += k  \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "枚举所有nums[i] & nums[j] 的个数，采用hash表进行统计\n",
    "然后遍历k，如果 & 为零，则直接统计个数\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter(x & y for x in nums for y in nums)\n",
    "        for x in nums:\n",
    "            for ky, val in cnt.items():\n",
    "                if x & ky == 0:\n",
    "                    ans += val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        two = Counter((x & y) for x in nums for y in nums)\n",
    "        ans = 0\n",
    "        for one in nums:\n",
    "            for mask, times in two.items():\n",
    "                if (one & mask) == 0:\n",
    "                    ans += times\n",
    "        return ans\n",
    "\n",
    "# 作者：LetMeFly\n",
    "# 链接：https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/solutions/2146568/letmefly-982an-wei-yu-wei-ling-de-san-yu-071t/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(x & y for x in nums for y in nums)\n",
    "        return sum(c for x, c in cnt.items() for y in nums if x & y == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        result = 0\r\n",
    "        \r\n",
    "        cnt = Counter()\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(n):\r\n",
    "                cnt[nums[i] & nums[j]]+=1\r\n",
    "        \r\n",
    "        \r\n",
    "        # i != j != k\r\n",
    "        for i in range(n):\r\n",
    "            x = nums[i]\r\n",
    "            sub = x = x ^ 0xffff\r\n",
    "            while True:\r\n",
    "                if sub in cnt:\r\n",
    "                    result += cnt[sub]\r\n",
    "                if sub == 0:\r\n",
    "                    break\r\n",
    "                sub = (sub - 1) & x\r\n",
    "    \r\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        x = {}\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                v = nums[i] & nums[j]\n",
    "                if v not in x:\n",
    "                    x[v] = 0\n",
    "                x[v] += 1\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            for v in x:\n",
    "                if v & nums[i] == 0:\n",
    "                    result += x[v]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        n = len(nums)\n",
    "        freq = {}\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                and_result = nums[i] & nums[j]\n",
    "                freq[and_result] = freq.get(and_result, 0) + 1\n",
    "            \n",
    "        for k in range(n):\n",
    "            for key in freq:\n",
    "                if nums[k] & key == 0:\n",
    "                    count += freq[key]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter((x & y) for x in nums for y in nums)  \n",
    "        answer = 0\n",
    "        for n in nums:\n",
    "            if n == 0:\n",
    "                answer += len(nums) * len(nums)\n",
    "                continue\n",
    "            for mask, freq in cnt.items():\n",
    "                if (n & mask) == 0:\n",
    "                    answer += freq\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        rec = []\n",
    "        n = len(nums)\n",
    "        c = Counter()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                c[nums[i] & nums[j]] += 1\n",
    "        ans = 0\n",
    "        u = (1 << 16) - 1\n",
    "        for x in nums:\n",
    "            # 只能在补集中取\n",
    "            mask = u ^ x\n",
    "            y = mask\n",
    "            while y > 0:\n",
    "                ans += c[y]\n",
    "                y = (y - 1) & mask\n",
    "            ans += c[0]\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        l = len(nums)\n",
    "        repo = {}\n",
    "        for i in range(l):\n",
    "            for j in range(l):\n",
    "                if (nums[i] & nums[j]) in repo:\n",
    "                    repo[nums[i] & nums[j]] += 1\n",
    "                else:\n",
    "                    repo[nums[i] & nums[j]] = 1\n",
    "        \n",
    "        for k in range(l):\n",
    "            for mul in repo:\n",
    "                if not (nums[k] & mul):\n",
    "                    count += repo[mul]\n",
    "                    \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        \"\"\" Bitmask \n",
    "        我们可以先枚举任意两个数x和y，用哈希表或数组cnt统计它们的按位与结果x&y出现的次数\n",
    "        然后我们枚举x和y的按位与结果xy，再枚举z，如果xy&z=0，则将cnt[xy]的值加入答案\n",
    "        \"\"\"\n",
    "\n",
    "        cnt = Counter(i & j for i in nums for j in nums)\n",
    "\n",
    "        ans = 0 \n",
    "        for z in nums:\n",
    "            for xy, v in cnt.items():\n",
    "                if xy & z == 0:\n",
    "                    ans += v \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        n, cnts = len(nums), collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                cnts[nums[i] & nums[j]] += 1\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            for val in cnts:\n",
    "                if num & val == 0: ans += cnts[val]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        cnt = Counter((x & y) for x in nums for y in nums)\n",
    "        \n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            sub = x = x ^ 0xffff\n",
    "            while True:\n",
    "                if sub in cnt:\n",
    "                    ans += cnt[sub]\n",
    "                if sub == 0:\n",
    "                    break\n",
    "                sub = (sub - 1) & x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countTriplets(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        result = 0\r\n",
    "        \r\n",
    "        cnt = Counter()\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(n):\r\n",
    "                cnt[nums[i] & nums[j]]+=1\r\n",
    "        \r\n",
    "        \r\n",
    "        # i != j != k\r\n",
    "        for i in range(n):\r\n",
    "            x = nums[i]\r\n",
    "            sub = x = x ^ 0xffff\r\n",
    "            while True:\r\n",
    "                if sub in cnt:\r\n",
    "                    result += cnt[sub]\r\n",
    "                if sub == 0:\r\n",
    "                    break\r\n",
    "                sub = (sub - 1) & x\r\n",
    "    \r\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "用字典树来维护\n",
    "'''\n",
    "class Tree:\n",
    "    def __init__(self, depth = 16):\n",
    "        self.dp = depth\n",
    "        self.had = [None, 0, None, 0]\n",
    "    def add(self, num):\n",
    "        cur = self.had\n",
    "        for i in range(self.dp):\n",
    "            if num & 1 == 1:\n",
    "                if i == self.dp - 1:\n",
    "                    cur[-1] += 1\n",
    "                if cur[2] == None and i < self.dp - 1:\n",
    "                    cur[2] = [None, 0, None, 0]\n",
    "                cur = cur[2]\n",
    "            else:\n",
    "                if i == self.dp - 1:\n",
    "                    cur[1] += 1\n",
    "                if cur[0] == None and i < self.dp - 1:\n",
    "                    cur[0] = [None, 0, None, 0]\n",
    "                cur = cur[0]\n",
    "            num >>= 1\n",
    "            \n",
    "\n",
    "    def cnt(self, mask, i, cur):\n",
    "        if cur == None:\n",
    "            return 0\n",
    "        if i == 15:\n",
    "            if mask & (1 << 15):\n",
    "                return cur[1]\n",
    "            else:\n",
    "                return cur[1] + cur[-1]\n",
    "\n",
    "        ans = 0\n",
    "        if mask & (1 << i):\n",
    "\n",
    "            ans += self.cnt(mask, i+1, cur[0])\n",
    "\n",
    "        else:\n",
    "\n",
    "            ans += self.cnt(mask, i+1, cur[0])\n",
    "\n",
    "            ans += self.cnt(mask, i+1, cur[2]) \n",
    "\n",
    "        return ans\n",
    "                  \n",
    "                    \n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        three = Tree()\n",
    "        two = Tree()\n",
    "        n = len(nums)\n",
    "        ans = nums.count(0)\n",
    "        for j in range(n):\n",
    "\n",
    "            cnt3 = three.cnt(nums[j], 0, three.had)\n",
    "\n",
    "            cnt2 = two.cnt(nums[j], 0, two.had)\n",
    "            \n",
    "            ans += (cnt2 + cnt3) * 6\n",
    "\n",
    "            for i in range(j):\n",
    "                three.add(nums[i] & nums[j])\n",
    "            two.add(nums[j])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "用字典树来维护\n",
    "'''\n",
    "class Tree:\n",
    "    def __init__(self, depth = 16):\n",
    "        self.dp = depth\n",
    "        self.had = [None, 0, None, 0]\n",
    "        self.mask = 0\n",
    "    def add(self, num):\n",
    "        cur = self.had\n",
    "        for i in range(self.dp):\n",
    "            if num & 1 == 1:\n",
    "                if i == self.dp - 1:\n",
    "                    cur[-1] += 1\n",
    "                if cur[2] == None and i < self.dp - 1:\n",
    "                    cur[2] = [None, 0, None, 0]\n",
    "                cur = cur[2]\n",
    "            else:\n",
    "                if i == self.dp - 1:\n",
    "                    cur[1] += 1\n",
    "                if cur[0] == None and i < self.dp - 1:\n",
    "                    cur[0] = [None, 0, None, 0]\n",
    "                cur = cur[0]\n",
    "            num >>= 1\n",
    "            \n",
    "\n",
    "    def cnt(self, i, cur):\n",
    "        if cur == None:\n",
    "            return 0\n",
    "        if i == 15:\n",
    "            if self.mask & (1 << 15):\n",
    "                return cur[1]\n",
    "            else:\n",
    "                return cur[1] + cur[-1]\n",
    "\n",
    "        ans = 0\n",
    "        if self.mask & (1 << i):\n",
    "\n",
    "            ans += self.cnt(i+1, cur[0])\n",
    "\n",
    "        else:\n",
    "\n",
    "            ans += self.cnt(i+1, cur[0])\n",
    "\n",
    "            ans += self.cnt(i+1, cur[2]) \n",
    "\n",
    "        return ans\n",
    "                  \n",
    "                    \n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        three = Tree()\n",
    "        two = Tree()\n",
    "        n = len(nums)\n",
    "        ans = nums.count(0)\n",
    "        for j in range(n):\n",
    "\n",
    "            three.mask = nums[j]\n",
    "            cnt3 = three.cnt(0, three.had)\n",
    "\n",
    "            two.mask = nums[j]\n",
    "            cnt2 = two.cnt(0, two.had)\n",
    "\n",
    "            ans += (cnt2 + cnt3) * 6\n",
    "\n",
    "            for i in range(j):\n",
    "                three.add(nums[i] & nums[j])\n",
    "            two.add(nums[j])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "用字典树来维护\n",
    "'''\n",
    "class Tree:\n",
    "    def __init__(self, depth = 16):\n",
    "        self.dp = depth\n",
    "        self.had = [None, 0, None, 0]\n",
    "    def add(self, num):\n",
    "        cur = self.had\n",
    "        for i in range(self.dp):\n",
    "            if num & 1 == 1:\n",
    "                if i == self.dp - 1:\n",
    "                    cur[-1] += 1\n",
    "                if cur[2] == None and i < self.dp - 1:\n",
    "                    cur[2] = [None, 0, None, 0]\n",
    "                cur = cur[2]\n",
    "            else:\n",
    "                if i == self.dp - 1:\n",
    "                    cur[1] += 1\n",
    "                if cur[0] == None and i < self.dp - 1:\n",
    "                    cur[0] = [None, 0, None, 0]\n",
    "                cur = cur[0]\n",
    "            num >>= 1\n",
    "            \n",
    "\n",
    "    def cnt(self, mask, i, cur):\n",
    "        if cur == None:\n",
    "            return 0\n",
    "        if i == 15:\n",
    "            if mask & (1 << 15):\n",
    "                return cur[1]\n",
    "            else:\n",
    "                return cur[1] + cur[-1]\n",
    "\n",
    "        ans = 0\n",
    "        if mask & (1 << i):\n",
    "\n",
    "            ans += self.cnt(mask, i+1, cur[0])\n",
    "\n",
    "        else:\n",
    "\n",
    "            ans += self.cnt(mask, i+1, cur[0])\n",
    "\n",
    "            ans += self.cnt(mask, i+1, cur[2]) \n",
    "\n",
    "        return ans\n",
    "                  \n",
    "                    \n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        three = Tree()\n",
    "        two = Tree()\n",
    "        n = len(nums)\n",
    "        ans = nums.count(0)\n",
    "        for j in range(n):\n",
    "            cnt3 = three.cnt(nums[j], 0, three.had)\n",
    "            ans += cnt3 * 6\n",
    "            cnt2 = two.cnt(nums[j], 0, two.had)\n",
    "            ans += cnt2 * 6\n",
    "\n",
    "            for i in range(j):\n",
    "                three.add(nums[i] & nums[j])\n",
    "            two.add(nums[j])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTriplets(self, nums: List[int]) -> int:\n",
    "        n, cnts = len(nums), collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            for val in range(max(nums) + 1):\n",
    "                if num & val == 0: cnts[val] += 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans += cnts[nums[i] & nums[j]]\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
